package com.waiting.leetcode;

/**
 * @Description
 * @Author bjweitingting
 * @Date 2019/3/12
 **/
public class KthSmallestElementInABST230 {

    public int kthSmallest(TreeNode root, int k) {
        int leftNum = countNode(root.left);
        if (leftNum == k - 1) {
            return root.val;
        } else if (leftNum >= k) {
            return kthSmallest(root.left, k);
        } else {
            return kthSmallest(root.right, k - leftNum - 1);
        }
    }

    public int countNode(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return 1 + countNode(root.left) + countNode(root.right);
    }
}
